package my.jwds.p208;

public class Trie {


    public static void main(String[] args) {
        //["Trie","insert","insert","insert","insert","insert","insert","search","search","search","search","search","search","search","search","search","startsWith","startsWith","startsWith","startsWith","startsWith","startsWith","startsWith","startsWith","startsWith"]
        //[[],["app"],["apple"],["beer"],["add"],["jam"],["rental"],["apps"],["app"],["ad"],["applepie"],["rest"],["jan"],["rent"],["beer"],["jam"],["apps"],["app"],["ad"],["applepie"],["rest"],["jan"],["rent"],["beer"],["jam"]]
        Trie trie = new Trie();
        trie.insert("app");
        trie.insert("apple");
        trie.insert("beer");
        trie.insert("add");
        trie.insert("jam");
        trie.insert("rental");
        boolean flag1 = trie.search("apple");   // 返回 True
        boolean flag2 = trie.search("app");     // 返回 False
        trie.startsWith("app"); // 返回 True
        trie.insert("app");
        boolean flag3 = trie.search("app");     // 返回 True
        System.out.println(flag1+","+flag2+","+flag3);

    }


    Trie[] childes ;


    boolean isEnd;

    public Trie() {
        childes = new Trie[26];
    }

    public void insert(String word) {
        Trie temp = this;
        for (int i = 0; i < word.length(); i++) {
            Trie next = temp.childes[word.charAt(i) - 'a'];
            if (next == null){
                next = new Trie();
                temp.childes[word.charAt(i) - 'a'] = next;
            }
            temp = next;
        }
        temp.isEnd = true;
    }

    public boolean search(String word) {
        Trie temp = this;
        for (int i = 0; i < word.length(); i++) {
            temp = temp.childes[word.charAt(i) - 'a'];
            if (temp == null)return false;
        }
        return temp.isEnd;
    }

    public boolean startsWith(String prefix) {
        Trie temp = this;
        for (int i = 0; i < prefix.length(); i++) {
            temp = temp.childes[prefix.charAt(i) - 'a'];
            if (temp == null)return false;
        }
        return true;
    }
}
